nLab complexity class

Idea

In computer science, the algorithms for solving computational problems use resources proportional to the size of their inputs. A complexity class is a collection of problems which all can be solved with similar resource usage.

More generally, many computers? are restricted in what they can compute, even with unlimited resources. A complexity class for a computer is the collection of all problems which can be solved by a program on that computer.

A complexity class might be defined for decision problems?, which only return true-or-false answers, but there are also definitions for function problems?.

Definition

Classical

Fix a model of computation?. Traditionally, we use the theory of Turing machines. The complexity class of this theory is the collection of all problems which can be decided by a term of the theory – a program of the model of computation.

When the theory is Turing-complete, then we have the complexity class R?. This class is composed of all problems whose answers form a recursive set.

Let a polynomial time bound on a program be a polynomial in natural numbers which takes the size of an input and returns the number of reductions required to compute the output. The theory of Turing machines with at least two tapes, restricted by polynomial time bounds, is associated with the complexity class PTIME?. Similarly, there are exponential time bounds, and a corresponding complexity class EXPTIME?.

For an example of a complexity class naturally generated by a type of computer, consider the theory of deterministic finite-state automata, or DFAs. Each DFA corresponds to a regular language, and the DFAs form a complexity class REG?. In terms of resource usage, REG corresponds to Turing machines using a constant amount of space.

Descriptive

Fix a fragment of higher-order logic. A query is a predicate on finite structures which can be expressed in the fragment. The descriptive complexity class of the fragment is the collection of queries, and the size of each input is the size of the corresponding finite structure.

For the fragment of first-order logic with an added least fixed point operator, the descriptive complexity class is PTIME?. Similarly, the fragment of second-order logic with a least fixed point operator gives the complexity class EXPTIME?.

Second-order logic with existential quantification but not universal quantification yields the complexity class NPTIME?.

Properties

(…)

Examples

• The complexity class R? corresponds to the height of computability according to the Church-Turing thesis.

• The classes PTIME? and NPTIME? are clearly related, but the exact details are elusive. The question of P vs NP? is central to computer science.

• The complexity class REG? describes both deterministic and non-deterministic finite-state automata (DFAs and NFAs) because DFAs and NFAs are equivalent in computational power. In practice, this has led to the popularity of regular languages and regular expressions? in computer science. The McNaughton-Yamada-Thompson algorithm and Glushkov’s algorithm send regular languages to equivalent NFAs, and Kleene’s algorithm sends NFAs to equivalent regular languages.

• quantum complexity classes:

  BQP for default quantum computers

  PostBQP

  DQC1 (“one clean qbit”),

  (…)

Related entries

• descriptive complexity theory?
• timed set

References

• Wikipedia, Complexity class, P versus NP problem